package com.arcgis.demo;

import java.math.BigDecimal;
import java.math.BigInteger;

public class BigSquareRoot {
	final static BigInteger HUNDRED = BigInteger.valueOf(100);

	private static BigDecimal sqrt(BigDecimal number, int scale,
			int roundingMode) {
		if (number.compareTo(BigDecimal.ZERO) < 0)
			throw new ArithmeticException("sqrt with negative");
		BigInteger integer = number.toBigInteger();
		StringBuffer sb = new StringBuffer();
		String strInt = integer.toString();
		int lenInt = strInt.length();
		if (lenInt % 2 != 0) {
			strInt = '0' + strInt;
			lenInt++;
		}
		BigInteger res = BigInteger.ZERO;
		BigInteger rem = BigInteger.ZERO;
		for (int i = 0; i < lenInt / 2; i++) {
			res = res.multiply(BigInteger.TEN);
			rem = rem.multiply(HUNDRED);
			BigInteger temp = new BigInteger(strInt.substring(i * 2, i * 2 + 2));
			rem = rem.add(temp);
			BigInteger j = BigInteger.TEN;
			while (j.compareTo(BigInteger.ZERO) > 0) {
				j = j.subtract(BigInteger.ONE);
				if (((res.add(j)).multiply(j)).compareTo(rem) <= 0) {
					break;
				}
			}
			res = res.add(j);
			rem = rem.subtract(res.multiply(j));
			res = res.add(j);
			sb.append(j);
		}
		sb.append('.');
		BigDecimal fraction = number.subtract(number.setScale(0,
				BigDecimal.ROUND_DOWN));
		int fracLen = (fraction.scale() + 1) / 2;
		fraction = fraction.movePointRight(fracLen * 2);
		String strFrac = fraction.toPlainString();
		for (int i = 0; i <= scale; i++) {
			res = res.multiply(BigInteger.TEN);
			rem = rem.multiply(HUNDRED);
			if (i < fracLen) {
				BigInteger temp = new BigInteger(strFrac.substring(i * 2,
						i * 2 + 2));
				rem = rem.add(temp);
			}
			BigInteger j = BigInteger.TEN;
			while (j.compareTo(BigInteger.ZERO) > 0) {
				j = j.subtract(BigInteger.ONE);
				if (((res.add(j)).multiply(j)).compareTo(rem) <= 0) {
					break;
				}
			}
			res = res.add(j);
			rem = rem.subtract(res.multiply(j));
			res = res.add(j);
			sb.append(j);
		}
		return new BigDecimal(sb.toString()).setScale(scale, roundingMode);
	}

	/**
	 * 
	 * @param number
	 * @param scale
	 * @return
	 */
	public static BigDecimal sqrt(BigDecimal number, int scale) {
		return sqrt(number, scale, BigDecimal.ROUND_HALF_UP);
	}

	public static BigDecimal sqrt(BigDecimal number) {
		int scale = number.scale() * 2;
		if (scale < 50)
			scale = 50;
		return sqrt(number, scale, BigDecimal.ROUND_HALF_UP);
	}

	public static void main(String args[]) {
		BigDecimal num = new BigDecimal(9);
		int scale = 10000;
		long start = System.currentTimeMillis();
		BigDecimal root = sqrt(num, scale);// 79.89993742175271
		System.out.println("1:"+((System.currentTimeMillis()-start)/1000/60)+"min");
		//System.out.println(root);
		//System.out.println(root.pow(2));
		long start2 = System.currentTimeMillis();
		BigDecimal root2 = sqrt2(num, scale);
		System.out.println("2:"+((System.currentTimeMillis()-start2)/1000/60)+"min");
		System.out.println("root.compareTo(root2) = "+root.compareTo(root2));
		//System.out.println();
	}
	
	public static BigDecimal sqrt2(BigDecimal val, int scale){
		int i = 0;
		BigDecimal number = new BigDecimal(1);
		int n = 100;
		if(scale>n){
			n = scale;
		}
		while(i<=n){
			BigDecimal b1 = val.divide(number, scale, BigDecimal.ROUND_HALF_UP);
			BigDecimal b2 = b1.subtract(number);
			BigDecimal b3 = b2.divide(new BigDecimal(2), scale, BigDecimal.ROUND_HALF_UP);
			number = number.add(b3);
			i++;
		}
		return number;
	}
}